//Given an array of words and a width maxWidth, format the text such that each l
//ine has exactly maxWidth characters and is fully (left and right) justified. 
//
// You should pack your words in a greedy approach; that is, pack as many words 
//as you can in each line. Pad extra spaces ' ' when necessary so that each line h
//as exactly maxWidth characters. 
//
// Extra spaces between words should be distributed as evenly as possible. If th
//e number of spaces on a line do not divide evenly between words, the empty slots
// on the left will be assigned more spaces than the slots on the right. 
//
// For the last line of text, it should be left justified and no extra space is 
//inserted between words. 
//
// Note: 
//
// 
// A word is defined as a character sequence consisting of non-space characters 
//only. 
// Each word's length is guaranteed to be greater than 0 and not exceed maxWidth
//. 
// The input array words contains at least one word. 
// 
//
// 
// Example 1: 
//
// 
//Input: words = ["This", "is", "an", "example", "of", "text", "justification."]
//, maxWidth = 16
//Output:
//[
//   "This    is    an",
//   "example  of text",
//   "justification.  "
//] 
//
// Example 2: 
//
// 
//Input: words = ["What","must","be","acknowledgment","shall","be"], maxWidth = 
//16
//Output:
//[
//  "What   must   be",
//  "acknowledgment  ",
//  "shall be        "
//]
//Explanation: Note that the last line is "shall be    " instead of "shall     b
//e", because the last line must be left-justified instead of fully-justified.
//Note that the second line is also left-justified becase it contains only one w
//ord. 
//
// Example 3: 
//
// 
//Input: words = ["Science","is","what","we","understand","well","enough","to","
//explain","to","a","computer.","Art","is","everything","else","we","do"], maxWidt
//h = 20
//Output:
//[
//  "Science  is  what we",
//  "understand      well",
//  "enough to explain to",
//  "a  computer.  Art is",
//  "everything  else  we",
//  "do                  "
//] 
//
// 
// Constraints: 
//
// 
// 1 <= words.length <= 300 
// 1 <= words[i].length <= 20 
// words[i] consists of only English letters and symbols. 
// 1 <= maxWidth <= 100 
// words[i].length <= maxWidth 
// 
// Related Topics 字符串 
// 👍 136 👎 0


package leetcode.editor.cn;

import java.util.ArrayList;
import java.util.List;

//Java：Text Justification
class P68TextJustification {
    public static void main(String[] args) {
        Solution solution = new P68TextJustification().new Solution();
        // TO TEST
        System.out.println(solution.fullJustify(new String[]{"Science", "is", "what", "we", "understand", "well",
                "enough", "to", "explain", "to", "a", "computer.",
                "Art", "is", "everything", "else", "we", "do"}, 20));
//        System.out.println(solution.fullJustify(new String[]{"ask",
//                "not","what","your","country","can","do","for","you","ask","what",
//                "you","can","do","for","your","country"},
//                16));
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public List<String> fullJustify(String[] words, int maxWidth) {
            List<String> result = new ArrayList<>();
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < words.length; i++) {
                String word = words[i];
                if (sb.length() == 0) {
                    sb.append(word);
                } else if (sb.length() + 1 + word.length() <= maxWidth) {
                    sb.append(" ").append((word));
                } else {
                    String string = sb.toString();
                    String[] arr = string.split(" ");
                    int wordLen = 0;
                    for (String s : arr) {
                        wordLen += s.length();
                    }
                    int space = maxWidth - wordLen;
                    int wordsNum = arr.length;
                    if (wordsNum <= 2) {
                        if (wordsNum == 1) {
                            for (int j = sb.length(); j < maxWidth; j++) {
                                sb.append(" ");
                            }
                        } else {
                            int index = sb.indexOf(" ");
                            for (int j = 0; j < space - 1; j++) {
                                sb.insert(index, " ");
                            }
                        }
                    } else {
                        int avgNum = 0;
                        List<Integer> numList = new ArrayList<>();
                        if (space % (wordsNum - 1) == 0) {
                            avgNum = space / (wordsNum - 1);
                            for (int j = 0; j < wordsNum - 1; j++) {
                                numList.add(avgNum);
                            }
                        } else {
                            int index = 1;
                            while (index < wordsNum) {
                                avgNum = space / (wordsNum - index++) + 1;
                                numList.add(avgNum);
                                space -= avgNum;
                                if (space % (wordsNum - index) == 0) {
                                    avgNum = space / (wordsNum - index);
                                    for (int j = 0; j < wordsNum - index; j++) {
                                        numList.add(avgNum);
                                    }
                                    break;
                                }
                            }

                        }
                        sb = new StringBuilder();
                        sb.append(arr[0]);
                        for (int j = 1; j < arr.length; j++) {
                            int num = numList.get(j - 1);
                            for (int m = 0; m < num; m++) {
                                sb.append(" ");
                            }
                            sb.append(arr[j]);
                        }
                    }
                    result.add(sb.toString());
                    sb = new StringBuilder();
                    sb.append(word);
                }
            }
            if (sb.length() != 0) {
                result.add(sb.toString());
            }
            String wordChange = result.get(result.size() - 1);
            String[] arr = wordChange.split(" ");
            sb = new StringBuilder();
            for (int i = 0; i < arr.length; i++) {
                sb.append(arr[i] + " ");
            }
            for (int i = sb.length(); i < maxWidth; i++) {
                sb.append(" ");
            }
            result.set(result.size() - 1, sb.toString().substring(0, maxWidth));
            return result;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}